1. Field of the Invention
This invention relates to computer network technology, and more particularly, to a two-stage computer network packet classification method and system which is designed for integration to a network system for classification of packets transmitted and received over the network system.
2. Description of Related Art
Packet classification is an important function of network systems for applications such as firewalls and intrusion detection, policy-based routing, and network service differentiations, for use to identify the attributes of all incoming packets based on their headers. When a networking device, such as an enterprise-class server or router, receives an incoming packet, the first step is to determine the type of the packet, such as what protocol is being used by the packet, what ToS (Type of Service) or QoS (Quality of Service) is to be assigned to the packet, the source and destination of the packet (which might be used to indicate, for example, whether the packet is coming from a malignant source), to name just a few.
In actual implementation, packet classification is realized by using a user-predefined rule database which specifies the mapping of predefined field values in the packet header to a set of rules, each rule representing a particular type of action or service that is to be performed on the packet. For example, if the source IP address of an incoming packet is matched to a rule that specifies an unauthorized IP address, the action to be performed on the incoming packet might be to discard the packet or to trace back to its originating source.
Typically, the total number of rules in a rule database might be in the range from several dozens to several thousands. Therefore, the hardware/software implementation of packet classification typically requires a huge amount of memory space for storage of the rule database and also requires a significant amount of access time to search through the rule database for matched rules. This drawback causes the implementation of packet classification to have low system performance.
In view of the aforementioned problem, it has been a research and development effort in the computer network industry for solutions that can implement the packet classification with reduced memory space and enhanced processing speed. Some research results have been disclosed in the following technical papers: [1] “Packet classification using hierarchical intelligent cuttings” authored by P. Gupta et al and published on IEEE Micro, vol. 20, no. 1, pp. 34-41, February 2000; [2] “Scalable Packet Classification” authored by Florin Baboescu et al and published on IEEE/ACM Transactions on networking, vol. 12, Issue 1, pp. 2-14, February 2005; and [3] “A modular approach to packet classification: algorithm and result” authored by T. Y. C. Woo and published on Proc. IEEE Infocom, vol. 3, pp. 1213-1222, March 2000; to name just a few. These papers teach the use of a so-called “decision tree” for finding a corresponding rule from the rule database for the input packet. One drawback to the use of the conventional decision tree, however, is that it requires a very large data amount for implementation, and thus needs a large amount of memory space for storage, which results in a low system performance.